/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package firstround09;

import java.io.IOException;
import static chanlib.Chan_IO.*;

/**
 * @author robit
 */
public class CrossingTheRoad{
    /*
      All neccesary to be defined
      including:
      variable, inner class
    */
    // static int A;
    // static void B();
    // static class C

    /*
       One calculation fits all of the cases.
    */
    static void preReckon(){
        return;
    }
    static long MAX=2l*10000000*4*20*20;
    /*
      calculate the answer
    */
    private static void reckon(int line) {
        int N=Int();
        int M=Int();
        long S[][]=new long[N][M];
        long W[][]=new long[N][M];
        long T[][]=new long[N][M];

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                S[i][j]=Long();W[i][j]=Long();T[i][j]=Long();
            }
        }
        // Use long to avoid integer overflow
        long bestTime[][]=new long[2*N][2*M];
        for(int i=0;i<2*N;i++)
        for(int j=0;j<2*M;j++)
        {bestTime[i][j]=MAX;}
        bestTime[2*N-1][0]=0;

        final int[] di={0,-1,0,1};
        final int[] dj={1,0,-1,0};
        for(int r=0;r<4*N*M;r++){
            for(int i=0;i<2*N;i++)
            for(int j=0;j<2*M;j++)
            {
                for(int dir=0;dir<4;dir++){
                    int ii=i+di[dir],jj=j+dj[dir];
                    if(ii<0||ii>=2*N||jj<0||jj>=2*M)continue;
                    // update bestTime [ii][jj]
                    long weigh=0;
                    if(ii/2==i/2&&jj/2==j/2){
                        long t=(bestTime[i][j]-T[i/2][j/2])%(S[i/2][j/2]+W[i/2][j/2]);
                        if(t<0)t+=S[i/2][j/2]+W[i/2][j/2];
                        switch(dir){
                            case 0: case 2:
                                if(t>=S[i/2][j/2])weigh=1;//walk
                                else weigh=(S[i/2][j/2]-t)+1;//wait and walk
                                break;
                            case 1: case 3:
                                if(t<S[i/2][j/2])weigh=1;
                                else weigh=(S[i/2][j/2]+W[i/2][j/2]-t)+1;
                                break;
                        }
                    }else weigh=2;

                    if(bestTime[ii][jj]>bestTime[i][j]+weigh){
                            bestTime[ii][jj]=bestTime[i][j]+weigh;
                    }
                }
            }
        }

        long ans=bestTime[0][2*M-1];

        String output=String.format("Case #%d: %d",line,ans);
        writeln(output, OUTFILE);
        println(output);
        //writeln(String.format("N=%d K=%d\n%s", N, K, ans),ANALFILE);
        //println(output);
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        /*
           Pre-computing for all cases
        */

        // Just in case!
        //preReckon();
        //while((char)read()!='P');

        /*
          Input-output
        */
        boolean test=false;
        boolean small=false;
        String prob="B";
        String filename;
        if(test) filename="test";
        else{
            if(small) filename=prob+"-small-practice";
            else filename=prob+"-large-practice";
        }
        try {
            /*
               Init IO,plus determination of input line number
             */
            int lineNums = initFileIO(filename);
            for (int i = 1; i <= lineNums; i++) {
                reckon(i);
            }
        } finally {
            endIO();
        }
    }

}
